//
// Created by wenyaxi on 24-10-29.
//
#include <common.h>
using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        pair<int, int> max_pair;
        int max_len = -1;
        for (int i = 0; i < s.length(); i++) {
            auto res_pair = findPalindrome(s, i, i);
            int tmp_len = res_pair.second - res_pair.first + 1;
            if (tmp_len > max_len) {
                max_len = tmp_len;
                max_pair = res_pair;
            }
        }

        for (int i = 0; i < s.length() - 1; i++) {
            auto res_pair = findPalindrome(s, i, i + 1);
            int tmp_len = res_pair.second - res_pair.first + 1;
            if (tmp_len > max_len) {
                max_len = tmp_len;
                max_pair = res_pair;
            }
        }
        return s.substr(max_pair.first, max_pair.second - max_pair.first + 1);
    }

    static pair<int, int> findPalindrome(const string &s, int left, int right) {
        for (;;) {
            if (left < 0 || right >= s.size() || s[left] != s[right]) {
                left++;
                right--;
                return make_pair(left, right);
            }
            left--;
            right++;
        }
    }
};

int main() {
    Solution s;
    //"babad"
    //"cbbd"
    auto find_palindrome = s.longestPalindrome("babad");
    cout << find_palindrome << endl;
    return 0;
}
